package medium.array;

/**
 * <a href="https://leetcode.cn/problems/insert-interval/">57. 插入区间</a>
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
 * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
 * 示例 1：
 *   输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
 *   输出：[[1,5],[6,9]]
 * 示例 2：
 *   输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
 *   输出：[[1,2],[3,10],[12,16]]
 *   解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
 * 示例 3：
 *   输入：intervals = [], newInterval = [5,7]
 *   输出：[[5,7]]
 * 示例 4：
 *   输入：intervals = [[1,5]], newInterval = [2,3]
 *   输出：[[1,5]]
 * 示例 5：
 *   输入：intervals = [[1,5]], newInterval = [2,7]
 *   输出：[[1,7]]
 * 提示：
 *   0 <= intervals.length <= 10^4
 *   intervals[i].length == 2
 *   0 <= intervals[i][0] <= intervals[i][1] <= 10^5
 *   intervals 根据 intervals[i][0] 按 升序 排列
 *   newInterval.length == 2
 *   0 <= newInterval[0] <= newInterval[1] <= 10^5
 * @author 刘学松
 * @date 2023-08-28 15:15
 */
public class 插入区间 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int length = intervals.length;
        if (length == 0) {
            return new int[][]{newInterval};
        }
        boolean cover = false;
        int left = newInterval[0], right = newInterval[1], start=-1,end=-1, last = -1, cur=-1;
        for (int i = 0; i < length; i++) {
            int[] interval = intervals[i];
            cur = interval[0];
            int bl = cur, br = interval[1];

            if (bl <= left && left <= br) {
                cover = true;
                start=i;
            } else if (last < left && left < cur) {
                if (last < right && right < cur) {
                    start = end = i;
                    break;
                } else {
                    cover = true;
                    start=i;
                    intervals[i][0] = left;
                }
            }
            if (bl <= right && right <= br) {
                cover = true;
                end = i;
                break;
            } else if (last < right && right < cur) {
                if (last < left && left < cur) {
                    start = end = i;
                    break;
                } else {
                    cover = true;
                    end=i-1;
                    intervals[i-1][1] = right;
                    break;
                }
            }

            last = br;
        }
        if (!cover) {
            int[][] ans = new int[length+1][2];
            if (start == -1) {
                System.arraycopy(intervals, 0, ans, 0, length);
                ans[length] = newInterval;
            } else if (start == 0) {
                System.arraycopy(intervals, 0, ans, 1, length);
                ans[0] = newInterval;
            } else {
                System.arraycopy(intervals, 0, ans, 0, start);
                ans[start] = newInterval;
                System.arraycopy(intervals, start, ans, start + 1, length - start);
            }
            return ans;
        } else {
            if (end == start) {
                return intervals;
            } else {
                if (end == -1) {
                    end = length - 1;
                    intervals[end][1] = right;
                }
                int[][] ans = new int[length - end + start][2];
                System.arraycopy(intervals, 0, ans, 0, start);
                ans[start] = new int[] {intervals[start][0], intervals[end][1]};
                System.arraycopy(intervals, end+1, ans, start + 1, length - end - 1);
                return ans;
            }
        }
    }
}
